﻿// Moo University - Financial Aid POJ - 2010.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

//https://vjudge.net/problem/POJ-2010
/*
贝西注意到，虽然人类有很多大学可以上，但奶牛却没有。
为了解决这个问题，她和她的奶牛伙伴们成立了一所新大学，名为威斯康星农庄大学，简称 "Moo U"。

由于不希望招收比平均水平更笨的奶牛，创建者们创造了一个非常精确的入学考试，名为 "奶牛学术能力测试"（CSAT），分数范围在 1-2,000,000,000 之间。

事实上，大多数小牛都需要某种经济援助（0 <= aid <=100,000）。
政府不给小牛提供奖学金，所以所有的钱都必须来自大学有限的基金（基金总额为 F，0 <= F <= 2,000,000,000）。

更糟糕的是，武大的教室只能容纳C（N <= C <= 100,000 ）只申请入学的小牛中的N位。奇数 N（1 <= N <= 19,999 ） 。
她仍然希望录取的小牛 CSAT 分数的中位数越高越好。

回忆一下，大小为奇数的整数集合的中位数是它们排序后的中间值。
例如，集合 {3, 8, 9, 7, 5} 的中位数是 7，因为正好有两个值高于 7，两个值低于 7。

给定每头申请小牛的分数和所需的资助、要录取的小牛总数以及贝西用于资助的资金总额，

确定贝西通过谨慎录取一组最佳小牛所能获得的最大中位数分数。

输入
* 第 1 行： 三个空格分隔的整数 N、C 和 F

* 第 2...C+1 行：每行两个空格分隔的整数。第一个整数是小牛的 CSAT 分数；第二个整数是小牛需要的资助金额
输出
* 第 1 行： 一个整数，即贝西能达到的最高中值分数。如果没有足够的资金录取 N 头小牛，则输出-1。

样例

3 5 70
30 25
50 21
20 20
5 18
35 30

35



3 9 16
5 13
6 16
1 1
7 1
7 17
2 2
9 13
9 20
1 8

ans 7

Input：
5 10 10
3 3
1 7
6 1
4 10
3 1
8 3
7 10
8 1
7 7
7 9
Output：
6
Input：
5 10 10
10 1
10 3
1 2
7 6
3 3
10 2
5 5
2 4
3 2
4 10
Output:
10
Input:
5 10 10
10 6
7 1
5 3
1 1
3 3
4 6
6 4
3 1
8 5
9 5
Output:
5



1 5 10
30 25
50 21
20 20
5 18
35 10
无答案 自己看


3 5 3
4 10
5 10
6 1
7 1
8 1
无答案自己看


提示
输出示例：如果贝西接受 CSAT 分数为 5、35 和 50 的小牛，则中位数为 35。所需资助总额为 18 + 30 + 21 = 69 <= 70。
*/

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int n, C, F;
const int N = 100010;
struct COW {
	long long score;
	long long cost;
	int idx;
}cowsScore[N];

long long leftSum[N];
long long rightSum[N];

 


bool scoreFunc(const COW& a, const COW& b) {
	return a.score <  b.score; // 降序排列
}

int main() {
	cin >> n >> C >> F;
	for (int i = 0; i < C; i++) {
		cin >> cowsScore[i].score >> cowsScore[i].cost;
	}
	sort(cowsScore, cowsScore + C, scoreFunc);
	
	{
		priority_queue<int>  maxHeap; // 定义大根堆
		long long heapSum = 0;
		memset(leftSum, 0x3f, sizeof(leftSum));
		for (int i = 0; i < C; i++) {
			if (maxHeap.size() == n / 2) {
				leftSum[i] = heapSum;
			}

			if (maxHeap.size() < n / 2) {
				maxHeap.push(cowsScore[i].cost);
				heapSum += cowsScore[i].cost;
			}
			else if (maxHeap.size() == n / 2) {
				if (maxHeap.size() && maxHeap.top() > cowsScore[i].cost) {
					heapSum -= maxHeap.top();
					maxHeap.pop();
					maxHeap.push(cowsScore[i].cost);
					heapSum += cowsScore[i].cost;
				}
			}
		}
	}

	{
		priority_queue<int>  maxHeap; // 定义大根堆
		long long heapSum = 0;
		memset(rightSum, 0x3f, sizeof(rightSum));
		
		for (int i = C - 1; i >= 0; i--) {
			if (maxHeap.size() == n / 2) {
				rightSum[i] = heapSum;
			}

			if (maxHeap.size() < n / 2) {
				maxHeap.push(cowsScore[i].cost);
				heapSum += cowsScore[i].cost;
			}
			else if (maxHeap.size() == n / 2) {
				if (maxHeap.size() && maxHeap.top() > cowsScore[i].cost) {
					heapSum -= maxHeap.top();
					maxHeap.pop();
					maxHeap.push(cowsScore[i].cost);
					heapSum += cowsScore[i].cost;
				}
			}
		}
	}

	for (int i = C; i >= 0; i--) {
		if (leftSum[i] + rightSum[i] + cowsScore[i].cost <= F) {
			cout << cowsScore[i].score << endl;
			return 0;
		}
	}

	cout << -1 << endl;

	return 0;
}